package code201_300.code10_20;


import java.util.HashSet;
import java.util.Set;

/**
 * 给定一个整数数组，判断是否存在重复元素。
 *
 * 如果存在一值在数组中出现至少两次，函数返回 true 。如果数组中每个元素都不相同，则返回 false 。
 *
 * 输入: [1,2,3,1]
 * 输出: true
 *
 * 输入: [1,2,3,4]
 * 输出: false
 *
 */
public class _217containsDuplicate {

    /**
     * 思考，想到了之前的异或的方法，相同元素异或之后是0。
     * 思考了半天的位运算，结果发现题解是那么的纯真，没有优秀方法，只有排序或者哈希表
     *
     * 执行用时：     * 5 ms     * , 在所有 Java 提交中击败了     * 53.73%     * 的用户
     * 内存消耗：     * 45.7 MB     * , 在所有 Java 提交中击败了     * 6.32%     * 的用户
     *
     * @param nums
     * @return
     */
    public boolean containsDuplicate(int[] nums) {
        Set<Integer> res = new HashSet<Integer>();
        for(int i:nums)
            res.add(i);
        return res.size()!=nums.length;
    }

    /**
     * 归并排序，时间空间效率明显提升
     *
     * 执行用时：     * 3 ms     * , 在所有 Java 提交中击败了     * 99.36%     * 的用户
     * 内存消耗：     * 41.6 MB     * , 在所有 Java 提交中击败了     * 76.98%     * 的用户
     *
     */
    boolean res = false;
    public boolean containsDuplicate1(int[] nums) {
        if (nums.length < 2) {
            return false;
        }
        div(nums,0,nums.length - 1);
        return res;
    }
    public void div(int[] nums, int l, int r) {
        if (l < r && !res) {
            int mid = l + ((r - l) >> 1);
            div(nums, l, mid);
            div(nums, mid + 1, r);
            mergeSort(nums, l, mid, r);
        }
    }
    public void mergeSort(int[] nums,int l,int mid,int r) {
        if (res) return;
        int[] temp = new int[r - l + 1];
        int left = l,right = mid + 1;
        int index = 0;
        while (left <= mid && right <= r) {
            if (nums[left] == nums[right]) {
                res = true;
                return;
            }
            if (nums[left] > nums[right]) {
                temp[index++] = nums[right++];
            }else {
                temp[index++] = nums[left++];
            }
        }
        while (left <= mid) {
            temp[index++] = nums[left++];
        }
        while (right <= r) {
            temp[index++] = nums[right++];
        }
        for (int i = 0; i < temp.length; i++) {
            nums[i + l] = temp[i];
        }
    }
}
